

// 将数组分割成若干个子数组
// 将相邻的子数组归并成一个有序的数组
// 再将这些有序数组归并成一个整体有序的数组
// 需要创建一个新的数组

// 分解  divide 合并 merge

import { measureSort, testSort } from "hy-algokit";

export default function mergeSort (arr:number[]):number[] {
    // 递归的结束条件
    if (arr.length <= 1) return arr;
    // 1.分解(divide): 对数组进行分解(分解成两个小数组)
    // 8/2 = 4
    // 1.1 切割数组
    const mid = Math.floor(arr.length/2);// 向下取整
    
    const leftArr = arr.slice(0,mid);//左闭右开,拿到前四个
    const rightArr = arr.slice(mid);//只传入一个的话，会直接从当前索引切到末尾

    // 1.2 递归的切割leftArr和RightArr
    const newArrayLeft = mergeSort(leftArr);
    const newArrayRight = mergeSort(rightArr);

    // 2.合并(merge): 将两个子数组进行合并 (双指针)
    // 2.1定义双指针
    let newArray:number[] = [];
    let i = 0;
    let j = 0;
    // 当i小于长度时,
    while (i < newArrayLeft.length && j < newArrayRight.length) { 
        // 当左边的数小的时候
        if(newArrayLeft[i] <= newArrayRight[j]){
            newArray.push(newArrayLeft[i]);
            i++;
        }else{
            newArray.push(newArrayRight[j]);
            j++;
        }
    }
    // 当循环结束的时候，可能还有一边有剩余的数据未push进新数组
    // 循环完左边有剩余
    if(i <  newArrayLeft.length){
        newArray.push(...newArrayLeft.slice(i))
    }
    // 循环完右边还有剩余
    if(j < newArrayRight.length){
        newArray.push(...newArrayRight.slice(j))
    }
    return newArray;
}

testSort(mergeSort);
measureSort(mergeSort);